623E - Transforming Sequence - CodeForces Solution

#include <algorithm>
#include <iostream>
constexpr int N = 30010;
constexpr int MOD = 1e9 + 7;
using ull = unsigned long long;
int inv[N], fac[N], ifac[N];
void calculateLn(int *f, int n) {
    static int g[N];
    for (int i = 0; i < n; ++i) {
        ull c = 0;int r = 0;
        for (; r <= i - 18; r += 18) {
            for (int t = r; t < r + 18; ++t) {c += 1ull * f[i - t] * g[t];
            }c %= MOD;
        }while (r < i) {
            c += 1ull * f[i - r] * g[r];
            ++r;}g[i] = (1ll * (i + 1) * f[i + 1] % MOD - int(c % MOD) + MOD) % MOD;
    }f[0] = 0;
    for (int i = 1; i <= n; ++i) {f[i] = 1ll * g[i - 1] * inv[i] % MOD;}
}
void calculateExp(int *f, int n) {
    static int g[N];
    for (int i = 0; i < n; ++i) {g[i] = 1ll * (i + 1) * f[i + 1] % MOD;}
    f[0] = 1;for (int i = 0; i < n; ++i) {
        ull c = 0;int r = 0;
        for (; r <= i - 18 + 1; r += 18) {
            for (int t = r; t < r + 18; ++t) {
                c += 1ull * f[t] * g[i - t];} c %= MOD;
        }while (r <= i) {
            c += 1ull * f[r] * g[i - r];++r;
        }f[i + 1] = c % MOD * inv[i + 1] % MOD;}
}
int fastPower(int a, int b) {
    int ans = 1;int base = a;
    while (b) {
        if (b & 1) {
            ans = 1ll * ans * base % MOD;
        }base = 1ll * base * base % MOD;b >>= 1;
    }return ans;
}
int main() {
    long long sequenceLength;
    int maxNumber;
    std::cin >> sequenceLength >> maxNumber;
    if (sequenceLength > maxNumber) {
        std::cout << 0 << std::endl;
        return 0;
    }
    fac[0] = 1;
    for (int i = 1; i <= maxNumber + 1; ++i) {
        fac[i] = 1ll * fac[i - 1] * i % MOD;
    }
    ifac[maxNumber + 1] = fastPower(fac[maxNumber + 1], MOD - 2);
    for (int i = maxNumber + 1; i; --i) {
        ifac[i - 1] = 1ll * ifac[i] * i % MOD;
        inv[i] = 1ll * fac[i - 1] * ifac[i] % MOD;
    }
    int difference = maxNumber - sequenceLength;static int f[N];std::copy(ifac + 1, ifac + difference + 2, f);
    calculateLn(f, difference);for (int i = 0, r = 1; i <= difference; ++i, r = r * 2 % MOD) {
        if (r == 1) {f[i] = 1ll * f[i] * sequenceLength % MOD;
        } else {int v = 1ll * (fastPower(r, sequenceLength) - 1) * fastPower(r - 1, MOD - 2) % MOD;f[i] = 1ll * f[i] * v % MOD;
        }}f[1] = (f[1] + 1) % MOD;calculateExp(f, difference);
    std::cout << 1ll * fac[maxNumber] * f[difference] % MOD * fastPower(2, sequenceLength * (sequenceLength - 1) / 2) %MOD << std::endl;
    return 0;
}/*1694644654.7930725*/